1. Field of the Invention
The present invention consists in a method of routing a call in a private network with overflow to a public or other network.
The invention concerns private telecommunication networks. Such networks are formed of communication nodes connected by links carrying calls and/or signaling.
2. Description of the Prior Art
The Dijkstra algorithm is described in the literature on algorithms and calculates the shortest path between two nodes in a graph. The algorithm operates as follows: it considers a graph G with N nodes, which is valued, i.e. each existing path of which between two nodes i and j is assigned a value or weight I(i, j). it considers an outgoing node s of the graph G and an incoming node d; it seeks a path minimizing xcfx80 (s, d), the distance from s to d, i.e. the sum of the values of the connections connecting s to d. S is the subgraph of G formed of the nodes x for which the minimum path to s is known, and {overscore (S)} is its complement. xcex93i is the set of nodes adjoining a given node i.
Initially the subgraph S contains only the node s, and {overscore (S)} contains all the other nodes, assigned the following initial values:
xcfx80(s, i)=I(s, i) for i∈xcex93s, the parent node being s;
xcfx80(s, d)=∞, for the other nodes, which have no parent node.
An iteration of the algorithm is effected in the following manner.
If {overscore (S)} is empty, or if it contains only nodes i with xcfx80(s, i)=∞, the algorithm has finished.
Otherwise, the node n of {overscore (S)} is considered which is nearest the originating node, i.e. the node which minimizes xcfx80(s, i), i∈{overscore (S)}; this node is taken from {overscore (S)} and placed in S.
The nodes adjacent this node n are then considered and the algorithm calculates
xcfx80(s, n)+I(n, j), j∈xcex93n and j∈{overscore (S)};
If this quantity is less than xcfx80(s, j), then xcfx80(s, j) is updated:
xcfx80(s, j):=xcfx80(s, n)+I(n, j)
and the parent node of j is also updated, which becomes n.
This operation is carried out for all the nodes of xcex93n, after which {overscore (S)} is reordered.
In this way, all the nodes of the graph are progressively added to S, in order of increasing path length. To find a path to a given node d, the algorithm can be interrupted before it finishes, since the destination node a has been added to the subgraph S.
The validity of the algorithm is demonstrated by the following reductio ad absurdum argument. Consider the node n nearest {overscore (S)} which must be added to S. If there is a nearer path, that path starts from s and arrives at n and has a first node m in {overscore (S)}. Then:
xcfx80(s, m)+xcfx80(m, n) less than xcfx80(s, n)
and, since xcfx80(m, n) is positive or zero:
xcfx80(s, m) less than p(s, n)
which contradicts the hypothesis. It is also clear that xcfx80(s, m) has been calculated in a preceding iteration, when adding the parent of m to S.
The document by J. Eldin and K. P. Lathia xe2x80x9cLe RNIS appliquxc3xa9 au Centrex et au rxc3xa9seaux privxc3xa9s virtuelsxe2x80x9d [The ISDN applied to Centrex and to virtual private networks] contains a description of physical private networks and virtual private networks. As explained in the document, in a physical private network the various sites or nodes are connected by dedicated circuits but in a virtual private network each node is connected to the local switch nearest the public network, where appropriate software sets up the connections on demand. There are two variants of the virtual private network: on the one hand, semi-permanent connections can be provided, which are set up without dialing as soon as any of the nodes requires the circuit, and which always connect the same two points. Such may be the case in particular for signaling connections in an application on an integrated services digital network. On the other hand, switched connections can be provided, which can be set up only by dialing.
The remainder of the description considers only physical or virtual private networks formed of nodes connected by links, which can be of any type: dedicated connections, or links using an external network; the latter can be of any typexe2x80x94the public switched network, a public land mobile network, an integrated services digital network, another private network, etc. FIG. 1 shows one example of a private network of this kind. This network includes, for example, nodes 1 to 6; nodes 2 to 6 are connected to the public network 8 by circuit groups 12 to 16. The nodes are interconnected by links formed of private connections, shown in bold in the figure, or, as in the case of the link between nodes 5 and 6, by a link comprising only a signaling connection. For a digital link, each private connection comprises at least one access, formed by a signaling connection and a plurality of B channels. The link between nodes 5 and 6 in FIG. 1 comprises a signaling connection and no B channel; this is typical of a node corresponding to a branch office, for which the volume of traffic is not very high.
The problem of overflow, i.e. the problem of a call request that cannot be satisfied by the network because its resources are congested, arises in private networks. This problem can arise if the private links of the private network have a fixed capacity, rather than a capacity which is allocated dynamically and which is less than the possible maximum volume of traffic. Completing the corresponding call using the public network is known in itself. In other words, if a user at node 2 wants to contact a user at node 6, and if the private network is congested and cannot complete the call, the call is completed via circuit groups 12 and 16 and the public network. This can be the case, for example, if the connection between nodes 2 and 4 is congested. In FIG. 1, reference numeral 10 shows schematically a call of this kind via the public network. Overflow may also be necessary if the link in question has no B channel, as in the case of node 6 in FIG. 1.
This solution gives rise to the following problems. On the one hand, using the public network incurs a cost; on the other hand, it is not certain that there is an access group to the public network for all the nodes; in the FIG. 1 example, node 1 has no group providing access to the public network and as a result a call via the public network could be routed via group 12 of node 2 or group 13 of node 3.
The invention proposes a solution to the above problems; it manages overflows from the private network in a way that minimizes the cost of access to the public network and maximizes the use of resources of the private network. It applies not only to overflows to the public network, but also and more generally to overflows to any type of network external to the private network: switched public network, public land or satellite mobile network, another private network, etc.
To this end, the invention proposes a method of routing a call in a private network, with overflow to another network, which comprises calculating various routes for setting up said call, with one or more overflows to said other network, and choosing a route as a function of the overflow cost and the number of overflows.
In one embodiment of the invention the choice is made from routes having a number of overflows less than a predetermined threshold value.
This predetermined threshold value is advantageously chosen as a function of the maximum call setup time. In one embodiment of the invention the predetermined value is 3.
The choice is preferably made to minimize a cost vector of routing the call, the cost vector having as one component the charge incurred because of the overflows and as one component the load of the links of the private network.
A first vector can be less than a second vector if the cost component of the first vector is less than the cost component of the second vector and, if the cost components are equal, if the load component of the first vector is less than the load component of the second vector.
The sum vector of first and second vectors is advantageously defined as the vector in which each component is the sum of the corresponding components of the first and second vectors.
In one embodiment of the invention the various routes are calculated using the Dijkstra algorithm, allowing for the number of overflows.
A step of calculating the minimum number of overflows between a node of the private network and the destination node of the call using the Dijkstra algorithm can be provided.
In this case, during an iteration of the Dijkstra algorithm, a node is ignored if the sum of the number of overflows to that node and the minimum number of overflows to the destination node of the call is greater than the predetermined threshold value.
Other features and advantages of the invention will become apparent on reading the following description of embodiments of the invention, which is given by way of example and with reference to the accompanying drawings.